/**
 * @File    : threeSumClosest.cpp
 * @Brief   : 最接近的三数之和
 * @Link    : https://leetcode-cn.com/problems/3sum-closest/
 * @Author  : Wei Li
 * @Date    : 2021-08-11
*/

#include <iostream>
#include <vector>
#include <algorithm>

class Solution
{
public:
    int threeSumClosest(std::vector<int> &nums, int target)
    {
        std::sort(nums.begin(), nums.end());
        int n = nums.size();
        int best = 1e7;

        // 根据差值的绝对值来更新答案
        auto update = [&](int cur)
        {
            if (std::abs(cur - target) < std::abs(best - target))
            {
                best = cur;
            }
        };

        // 枚举 a
        for (int i = 0; i < n; ++i)
        {
            // 保证和上一次枚举的元素不相等
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }
            // 使用双指针枚举 b 和 c
            int j = i + 1, k = n - 1;
            while (j < k)
            {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果和为 target 直接返回答案
                if (sum == target)
                {
                    return target;
                }
                update(sum);
                if (sum > target)
                {
                    // 如果和大于 target，移动 c 对应的指针
                    int k0 = k - 1;
                    // 移动到下一个不相等的元素
                    while (j < k0 && nums[k0] == nums[k])
                    {
                        --k0;
                    }
                    k = k0;
                }
                else
                {
                    // 如果和小于 target，移动 b 对应的指针
                    int j0 = j + 1;
                    // 移动到下一个不相等的元素
                    while (j0 < k && nums[j0] == nums[j])
                    {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }
};

// -----------------------------
int main(int argc, char **argv)
{
    std::vector<int> nums{-1, 2, 1, -4};
    int target = 1;

    Solution solution;
    int three_sum_closest = solution.threeSumClosest(nums, target);
    std::cout << "The solution of this problem is " << three_sum_closest << std::endl;

    return 0;
}
